package JZ_Offer.algorithm.模拟;

import java.util.ArrayList;

/**
 * 顺时针打印矩阵
 *
 * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
 * 例如，如果输入如下4 X 4矩阵
 * 1  2  3  4
 * 5  6  7  8
 * 9  10 11 12
 * 13 14 15 16
 * 则依次打印出数字
 * 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
 *
 * @Author piper
 * @Date 2019/12/18 11:35 上午
 */
public class JZ29_顺时针打印矩阵 {

    /**
     * 定义四个变量 left，right，up，down 代表矩阵的四个边界
     * 依次按照 上，右，下，左 四个方面遍历 并缩减边界
     * 直到打印出所有数字
     */
    static ArrayList<Integer> printMatrix(int[][] matrix) {
        int left = 0, right = matrix[0].length - 1;
        int up = 0, down = matrix.length - 1;

        int maxLength = matrix[0].length * matrix.length;
        ArrayList<Integer> res = new ArrayList<>(maxLength);

        while (res.size() != maxLength) {
            // 遍历最上面一行
            for (int row = left; row <= right; row++) {
                res.add(matrix[up][row]);
            }
            up++;
            if (res.size() == maxLength) break;

            // 遍历最右面一列
            for (int col = up; col <= down; col++) {
                res.add(matrix[col][right]);
            }
            right--;
            if (res.size() == maxLength) break;

            // 遍历最下面一行
            for (int row = right; row >= left; row--) {
                res.add(matrix[down][row]);
            }
            down--;
            if (res.size() == maxLength) break;

            // 遍历最左边一列
            for (int col = down; col >= up; col--) {
                res.add(matrix[col][left]);
            }
            left++;
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        System.out.println(printMatrix(matrix));
    }
}
